package com.study.sort;

import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static com.study.sort.BubbleSort.exch;
import static com.study.sort.BubbleSort.greater;

// 插入排序
public class InsertionSort
{
    int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

    // // 2023新版数据结构与算法


    @Test
    void sort2()
    {
        insertion(arr, 1);
    }

    // low 表示待插入元素的索引，它的左侧是已经插入排序完成的区间
    private void insertion(int[] arr, int low)
    {
        if (low == arr.length) return;

        int t = arr[low];   // 先把 low 处的值取出，因为后面要做元素后移一位的操作
        int i = low - 1;
        // 找插入点，倒序遍历左侧有序区间，找小于等于待插入值的索引
        while (i >= 0 && arr[i] > t) {
            // 元素比插入值大，向后移一位
            arr[i + 1] = arr[i];
            // 继续向左找
            i--;
        }
        // 已经找到插入位置
        if (i + 1 != low)
            arr[i + 1] = t;

        insertion(arr, low + 1);
    }

    // // 2020版数据结构与算法
    @Test
    void sort1()
    {
        for (int i = 1; // 默认只有索引 0 这一个元素是有序的，待插入的元素从索引 1 开始
             i < arr.length; i++) {
            // 倒序遍历待插入元素左侧的有序区间，把待插入元素通过两两比较的方式交换到合适位置
            for (int j = i; j > 0; j--) {
                if (greater(arr[j - 1], arr[j])) {
                    exch(arr, j - 1, j);
                } else {
                    break;
                }
            }
        }
    }

    // // Java基础 入门到起飞 常见算法
    @Test
    void sort()
    {
        // 无序区间开始的索引，有序区间和无序区间的分界点
        int startIndex = -1;
        // 1、从左往右找出无序区间开始的索引
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > arr[i + 1]) {
                // 当前元素大于后一个元素，则有序区间结束，后一个索引就是无序区间开始位置
                startIndex = i + 1;
                break;
            }
        }
        // 2、无序区间的元素一一向左侧有序区间插入
        for (int i = startIndex; i < arr.length - 1; i++) {
            for (int j = i;
                 j > 0 && arr[j] < arr[j - 1];  // 当前元素比前一个元素小
                 j--) {
                // 交换 j 和 j - 1
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
    }

    @BeforeEach
    void printArrBefore()
    {
        System.out.println(Arrays.toString(arr));
    }

    @AfterEach
    void printArrAfter()
    {
        System.out.println(Arrays.toString(arr));
    }
}
